package practice;

/**
 * 假设我们有一个 n 乘以 n 的矩阵 w[n][n]。矩阵存储的都是正整数。棋子起始位置在左上角，终止位置在右下角。
 * 我们将棋子从左上角移动到右下角。每次只能向右或者向下移动一位。从左上角到右下角，会有很多不同的路径可以走。我们把每条路径经过的数字加起来看作路径的长度。
 */

public class ShortestPath2 {
    private int[][] nodes = new int[][]{{1, 3, 5, 9}, {2, 1, 3, 4}, {5, 2, 6, 7}, {6, 8, 4, 3}};
    private int minV = Integer.MAX_VALUE;

    private void getShortestPath() {
        int[][] state = nodes.clone();
        // 第一列全算出来
        for (int i = 1; i < nodes.length; i++) {
            state[i][0] += state[i - 1][0];
        }
        // 第一行全算出来
        for (int i = 1; i < nodes[0].length; i++) {
            state[0][i] += state[0][i - 1];
        }
        // 后面的就好办了
        for (int i = 1; i < nodes.length; i++) {
            for (int j = 1; j < nodes[0].length; j++) {
                state[i][j] += Math.min(state[i - 1][j], state[i][j - 1]);
            }
        }

        System.out.println(state[nodes.length - 1][nodes[0].length - 1]);
    }

    public static void main(String[] args) {
        ShortestPath2 shortestPath2 = new ShortestPath2();
        shortestPath2.getShortestPath();

    }
}
